/**
 * Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
 */
package com.xinpan.exercise;

//do again
public class LongestPalindrome {
    public String longestPalindrome(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int len = s.length();
        if(len == 0)
            return "";
            
        int[][] step = new int[len+1][len];
        for(int i = 0; i < len; i++)
        {
            step[0][i] = 0;
            step[1][i] = 1;
        }
            
            
        for(int i = 2; i <= len; i++)
        {
            for(int j = i-1; j < len; j++)
            {
                int wid = i;
                int req = wid - 2;
                if(j-wid+1 >= 0 && step[req][j-1] == req)
                {
                    if(s.charAt(j) == s.charAt(j-wid+1))
                        step[i][j] = wid;
                    else
                        step[i][j] = step[i-1][j];
                }
                else
                    step[i][j] = step[i-1][j];
            }
        }
        int max = 0;
        int pos = 0;
        for(int i = 0; i < len; i++)
        {
            if(step[i+1][i] > max)
            {
                max = step[i+1][i];
                pos = i - max + 1;
            }
        }
        return s.substring(pos, pos+max);
    }
    
    public static void main(String[] args)
    {
    	LongestPalindrome lp = new LongestPalindrome();
    	lp.longestPalindrome("bb");
    }
}
